
#ifndef __DOEPLUS_STRINGMAP_H__
#define __DOEPLUS_STRINGMAP_H__

#include <string>
#include <cstring>
#include <iostream>

namespace doeplus{

template<typename ContentType> class stringmap{

	private:
		typedef struct _Node{
			char *str;
			std::size_t strSize;
			ContentType *contentObject;
			_Node **subnodes;
			unsigned char *subnodemap;
			std::size_t subnodesSize;

			void copyString(const char* copyString,std::size_t stringSize=0){
				if(!stringSize){
					stringSize	= strlen(copyString);
				}
				char *newStr	= new char[stringSize+1];
				memcpy(newStr,copyString,stringSize);
				newStr[stringSize]	= 0;
				if(str){
					delete [] str;
				}
				str	= newStr;
				strSize	= stringSize;
			}

			_Node() : str(NULL),strSize(0),contentObject( NULL ),subnodes(NULL),subnodemap(NULL),subnodesSize(0){
			}

			_Node(const char *copyStr,ContentType *contentObject) : str(NULL),strSize(0),contentObject(contentObject),subnodes(NULL),subnodemap(NULL),subnodesSize(0){
				copyString(copyStr);
			}

			~_Node(){
				delete [] str;
				delete contentObject;
				for(std::size_t i(0);i<this->subnodesSize;++i){
					delete this->subnodes[i];
				}
				delete [] this->subnodes;
				delete [] this->subnodemap;
			}

		} Node;

		Node *root;

	public:
		class iterator{
			protected:
				friend class stringmap;

				Node *node;
				Node *lastNode;
				iterator(Node *node,Node *lastNode) : node(node),lastNode(lastNode) { }
			public:
				iterator() : node(NULL),lastNode(NULL) { }
				operator bool() const {
					if(node){
						if(node->contentObject){
							return true;
						}
					}
					return false;
				}
				ContentType* operator* (){
					if(node){
						return node->contentObject;
					}
					return NULL;
				}
		};


	public:
		stringmap() : root(new Node()){

		}
		~stringmap(){
			delete this->root;
		}

		iterator find(const char *key){

			Node *node	= this->root;
			const char *findStr	= key;
			bool found(false);
			unsigned char subnodePos;
			Node *subnode;
			const char *subnodeStr;

			while(*findStr){
				found=false;
				if(node->subnodemap){
					if(subnodePos = node->subnodemap[(unsigned char)*findStr]){
						--subnodePos;
						// Found the char in the map
						subnode	= node->subnodes[subnodePos];

						// Matched first character, meaning that this is the node of interrest
						//const char *subStr	= findStr;
						subnodeStr	= subnode->str+1;
						//std::size_t len(1);
						++findStr;
						// Check if the whole subnodes string match the string
						while(*subnodeStr==*findStr && *subnodeStr && *findStr){
							++subnodeStr;
							++findStr;
							//++len;
						}
						if(!*subnodeStr){
							// Subnodes string has ended
							if(!*findStr){
								// findStr has ended
								// Nodes are identical, return this subnode
								return iterator(subnode,subnode);
							}else{
								// Find String is not finished, lets look through subnodes
								node	= subnode;
								found	= true;
								--findStr;
							}
						}else{
							// subnode has not ended
							return iterator();
						}

					}

				}
				if(!found){
					// There where no matching subnodes in the subnode list
					return iterator();
				}

				++findStr;
			}

			return iterator();
		}
		iterator find(const std::string &key){
			return find(key.c_str());
		}

		ContentType& operator[](const std::string& key){
			ContentType tempContent;
			return *this->insert(key.c_str(),tempContent).node->contentObject;
		}

		iterator insert(const char *key,ContentType &contentObject){

			Node *node	= this->root;
			const char *findStr	= key;

			if(!*findStr){
				this->root->contentObject	= new ContentType(contentObject);
				return iterator(this->root,this->root);
			}

			unsigned char subnodePos;
			bool found(false);
			Node *subnode;
			const char *subnodeStr;
			std::size_t len;

			while(*findStr){
				found	= false;

				// Locate char in the nodes map
				if(node->subnodemap){
					if(subnodePos = node->subnodemap[(unsigned char)*findStr]){
						--subnodePos;
						// Found the char in the map
						subnode	= node->subnodes[subnodePos];

						// Matched first character, meaning that this is the node of interrest
						//const char *subStr	= findStr;
						subnodeStr	= subnode->str+1;
						len	= 1;
						++findStr;
						// Check if the whole subnodes string match the string
						while(*subnodeStr==*findStr && *subnodeStr && *findStr){
							++subnodeStr;
							++findStr;
							++len;
						}
						if(!*subnodeStr){
							// Subnodes string has ended
							if(!*findStr){
								// findStr has ended
								// Nodes are identical, replace contentObject
								delete subnode->contentObject;
								subnode->contentObject	= new ContentType(contentObject);
								return iterator(subnode,subnode);
							}else{
								// Find String is not finished, lets look through subnodes
								node	= subnode;
								found	= true;
								--findStr;
							}
						}else{
							// subnode string has not ended
							if(!*findStr){
								// But the findStr has ended
								// This would mean that it needs to split the subnode to a node with a subnode
								Node *oldSubNode	= subnode;
								Node *newNode		= new Node(findStr-len,new ContentType(contentObject));
								node->subnodes[subnodePos]	= newNode;
								newNode->subnodes	= new Node *[1];
								newNode->subnodesSize	= 1;
								newNode->subnodes[0]	= oldSubNode;
								newNode->subnodemap	= new unsigned char[256];
								memset( newNode->subnodemap, '\0', 256);
								//oldSubNode->str = oldSubNode->str.erase(0,len);
								//newNode->subnodemap[(unsigned char)oldSubNode->str.at(0)]	= 1;
								oldSubNode->copyString(oldSubNode->str,oldSubNode->strSize-len);
								newNode->subnodemap[(unsigned char)*oldSubNode->str]	= 1;
								return iterator(newNode,newNode);
							}else{
								// This means that the findStr and the subnodeStr does not match
								// and we have no match
								// We need to split the node to a node (without contentObject) and
								// with 2 subnodes
								Node *oldSubNode	= subnode;
								std::string startNodeName(oldSubNode->str,0,len);
								Node *newNode	= new Node(startNodeName.c_str(),NULL);
								node->subnodes[subnodePos]	= newNode;
								newNode->subnodes	= new Node *[2];
								newNode->subnodesSize	= 2;
								newNode->subnodes[0]	= oldSubNode;
								//oldSubNode->str = oldSubNode->str.erase(0,len);
								oldSubNode->copyString(oldSubNode->str,oldSubNode->strSize-len);
								newNode->subnodes[1]	= new Node(findStr,new ContentType(contentObject));

								newNode->subnodemap	= new unsigned char[256];
								memset( newNode->subnodemap, '\0', 256);

//								if(newNode->subnodes[0]->str.at(0) < newNode->subnodes[1]->str.at(0)){
									newNode->subnodemap[(unsigned char)*newNode->subnodes[0]->str]	= 1;
									newNode->subnodemap[(unsigned char)*newNode->subnodes[1]->str]	= 2;
/*								}else{
									newNode->subnodemap[newNode->subnodes[0]->str.at(0)]	= 2;
									newNode->subnodemap[newNode->subnodes[1]->str.at(0)]	= 1;
								}*/
								return iterator(newNode->subnodes[1],newNode->subnodes[1]);
							}
						}
					}

				}
				if(!found){
					// There where no matching subnodes in the subnode list
					// Add to the subnodes
					if(!node->subnodemap){
						node->subnodemap	= new unsigned char[256];
						memset( node->subnodemap, '\0', 256);

					}
					Node **oldnodelist	= node->subnodes;
					++node->subnodesSize;
					node->subnodes	= new Node *[node->subnodesSize];
					for(std::size_t i(0);i<node->subnodesSize-1;++i){
						node->subnodes[i]	= oldnodelist[i];
					}
					if(oldnodelist){
						delete [] oldnodelist;
					}
					node->subnodes[node->subnodesSize-1]	= new Node(findStr,new ContentType(contentObject));
					node->subnodemap[(unsigned char)*node->subnodes[node->subnodesSize-1]->str]	= node->subnodesSize;
					return iterator(node->subnodes[node->subnodesSize-1],node->subnodes[node->subnodesSize-1]);
				}

				++findStr;
			}

			return iterator();
		}

	private:
		void _printMap(Node *node,std::string space){
			std::cout << space << node->str << " = " << node->contentObject << " ";
			std::cout << "\n";

			for(int i(0);i<node->str.size();++i){
				space += " ";
			}
			for(std::size_t i(0);i<node->subnodesSize;++i){
				this->_printMap(node->subnodes[i],space);
			}
		}

		long _memSize(Node *node,long parentKeySize){
			long size(sizeof(Node));
			for(std::size_t i(0);i<node->subnodesSize;++i){
				size	+= this->_memSize(node->subnodes[i],parentKeySize+node->str.size());
			}
			if(node->subnodemap){
				size+=256;
			}
			size+=node->str.size() + node->subnodesSize*sizeof(void*);
			if(node->contentObject){
				size-= (parentKeySize+node->str.size());
			}
			return size;

		}

	public:
		void printMap(){
			this->_printMap(this->root,std::string());
		}
		long memSize(){
			return this->_memSize(this->root,0);
		}

};

}

#endif
